//
// Created by LiuYou on 2021/11/30.
//

#include <iostream>
#include <vector>
#include <iterator>


static void mergeTwoSide(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> help( right - left + 1 );
    int index = 0;

    int pLeft = left;
    int pRight = mid + 1;

    while (pLeft <= mid && pRight <= right) {
        if (arr[pLeft] <= arr[pRight]) {
            help[index++] = arr[pLeft++];
        } else {
            help[index++] = arr[pRight++];
        }
    }
    while (pLeft <= mid) {
        help[index++] = arr[pLeft++];
    }
    while (pRight <= right) {
        help[index++] = arr[pRight++];
    }

    for (int i = 0; i < help.size(); ++i) {
        arr[left + i] = help[i];
    }
}


static void sort(std::vector<int>& arr, int left, int right) {
    if (left == right) {
        return;
    } else {
        int mid = left + ((right - left) >> 1);
        sort( arr, left, mid );
        sort( arr, mid + 1, right );
        mergeTwoSide( arr, left, mid, right );
    }
}


/*
 * 并归排序。
 */
static void mergeSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    sort( arr, 0, arr.size() - 1 );
}


int main(int argc, char** argv) {
    std::vector<int> arr{3, 56, 1, 651, 6, 1, 4, 65, 61, 61, 46};
    mergeSort( arr );
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;


    return 0;
}
